package LinkedList;

public class _143_ReorderList {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode sNode = slow;
        ListNode bNode = head;
        //奇偶链表不同处理
        if(fast.next==null && sNode!=null){
            sNode = reverse(sNode);
        }else if(fast.next!=null){
            sNode = reverse(sNode.next);
        }
        while(bNode!=null && !(bNode.equals(sNode)) && !(bNode.next.equals(sNode))){
            ListNode bnext = bNode.next;
            ListNode snext = sNode.next;
            bNode.next = sNode;
            sNode.next = bnext;
            bNode = bnext;
            sNode = snext;
        }
        //处理最后两个数
        if(bNode!=null && !(bNode.equals(sNode)) && bNode.next.equals(sNode)){
            bNode.next = sNode;
        }
    }

    //反转后原链表顺序改变
    public ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
